//在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [3,4,3,3]
//输出：4
// 
//
// 示例 2： 
//
// 输入：nums = [9,1,7,9,7,9,7]
//输出：1 
//
// 
//
// 限制： 
//
// 
// 1 <= nums.length <= 10000 
// 1 <= nums[i] < 2^31 
// 
//
// 
//
// Related Topics 位运算 数组 👍 463 👎 0


package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

class 数组中数字出现的次数II {
    public static void main(String[] args) {
        Solution solution = new 数组中数字出现的次数II().new Solution();
        solution.singleNumber(new int[]{1,1,1,2,5,5,3,5,2,2,});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int singleNumber(int[] nums) {
            int ones = 0,twos = 0;
            for (int num :
                    nums) {
                ones = ones ^ num & ~twos;
                twos = twos ^ num & ~ones;
            }
            return ones;
        }

        
        public int singleNumber3(int[] nums) {
            Map<Integer, Boolean> map = new HashMap<>();
            for (int num : nums) {
                if (map.containsKey(num)){
                    map.put(num,false);
                }else {
                    map.put(num,true);
                }
            }
            for (Map.Entry<Integer, Boolean> entry:
                    map.entrySet()){
                if (entry.getValue()) {
                    return entry.getKey();
                }
            }
            return -1;
        }

        public int singleNumber2(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                if (map.containsKey(num)){
                    map.put(num,map.get(num) + 1);
                    if (map.get(num) == 3){
                        map.remove(num);
                    }
                }else {
                    map.put(num,1);
                }
            }
            for (Map.Entry<Integer, Integer> entry:
            map.entrySet()){
                return entry.getKey();
            }
            return -1;
        }

        public int singleNumber1(int[] nums) {
            int[] counts = new int[32];
            for (int num :
                    nums) {
                for (int i = 0; i < 32; i++) {
                    counts[i] += num & 1;
                    num >>>= 1;
                }
            }
            int res = 0;
            for (int i = 0; i < 32; i++) {
                res <<= 1;
                res |= (counts[31 - i]) % 3;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
